package com.sicheng.datastruct.linkedlist;


import java.util.Stack;

public class SingleLinkedNode {
    /**
     * 带头结点的单向链表结构
     * 1.一个头指针
     * 2.方法
     */
    private final HeroNode head = new HeroNode();

    public void addOnTail(HeroNode heroNode) {
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    public void update(HeroNode modified) {
        HeroNode temp = head;
        boolean isExist = true;
        while (true) {
            if (temp.next == null) {
                isExist = false;
                break;
            }
            if (temp.next.no == modified.no) {
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            temp.next.name = modified.name;
            temp.next.nickname = modified.nickname;
        } else System.out.println("指定节点不存在,无法修改");
    }

    public void deleteByNo(int no) {
        HeroNode temp = head;
        boolean isExist = true;
        while (true) {
            if (temp.next == null) {
                isExist = false;
                break;
            }
            if (temp.next.no == no) {
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            HeroNode remove = temp.next;
            temp.next = remove.next;
        } else System.out.println("指定节点不存在无法删除");
    }

    public void addByLevel(HeroNode heroNode) {

        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                addOnTail(heroNode);
                break;
            }

            if (temp.next.no > heroNode.no) {
                heroNode.next = temp.next;
                temp.next = heroNode;
                break;
            }
            if (temp.next.no == heroNode.no) {
                System.out.println("已存在，无法插入");
                return;
            }

            temp = temp.next;
        }

    }

    public void list() {
        HeroNode temp = head;
        while (true) {
            if (temp.next != null) {
                System.out.println(temp.next);
                temp = temp.next;
            } else break;
        }
    }

    /**
     * 统计有效节点个数
     */

    public int count() {
        int count = 0;
        HeroNode temp = head.next;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 新浪面试题
     * 查询单链表倒数第k个节点
     * 转化为查询正数第....
     * 1.得到链表的有效个数size
     * 2.查询第(size-k)+1个节点,(size-k)>=0
     */
    public HeroNode selectTheLastK(int k) {

        HeroNode temp = head.next;
        int count = 1, size = count();
        if ((size - k) < 0 || size == 0 || k <= 0)
            return null;
        while (count != (size - k + 1)) {
            temp = temp.next;
            count++;
        }
        return temp;
    }

    /**
     * 腾讯面试题
     * 单链表的反转
     * 思路：
     * 1. 如果单链表为空或单链表中只有头结点，那么单链表不需要逆置，如果单链表中只有一个元素，
     * 逆置之后它的位置还是不会改变，所以可以不逆置。
     * <p>
     * <p>
     * 2.当单链表中有2个或两个以上的元素时，从第1个元素断开，
     * 令它的next为空，依次访问第2个元素到第n个元素，
     * 当访问到其中的任意一个元素时，将它插入到头结点之后，也就是把它插入到第1个位置，
     * 这样原始的第1个元素就会被后面的n-1个元素插入到它的前面，
     * 原始的第2个元素就会被后面的n-2个元素插入到它的前面，...直到原始的第n个元素插入到第1个位置。
     * 这样就实现了带头结点的单链表的就地逆置。
     */
    public void reverse() {
        //空表或只要1个有效节点没必要反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode firstNode = head.next;
        HeroNode temp = firstNode.next;
        firstNode.next = null;
        //接下来,单链表的有效节点大于2
        //从第二个元素开始遍历，将当前节点移到firstNode前面
        while (temp.next != null) {
            HeroNode next = temp.next;
            temp.next = head.next;
            head.next = temp;
            temp = next;
        }
        temp.next = head.next;
        head.next = temp;
    }


    /**
     * 从尾到头打印单链表
     * 1.通过栈结构的先进后出原理，存入栈中
     * 2.从栈顶弹出节点
     */
    public void reversePrint(){
        HeroNode temp =head;
        Stack<HeroNode> stack = new Stack<>();
        while (temp.next!=null){
            stack.add(temp.next);
            temp=temp.next;
        }

        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }


}

class HeroNode {

    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    public HeroNode() {
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }

}
